1. Field of the Invention
The invention relates in general to signalprocessing apparatus and in particular to networks for determining the Mth-largest of an input data set. The invention has special relevance in those environments, such as image processing, where it is advantageous to perform this value determination in real time.
2. Description of the Prior Art
Presented here is the concept of an ordinal-value filter which determines which one of a set of R applied data values is the Mth-largest. When R is odd and M is made equal to (R+1)/2, the Mth-largest becomes the "middle" value of the data set, having in general an equal number of other data values both larger than and smaller than itself. Such a middle value is designated the median. A median filter is one which determines or selects this median value from an input data set.
Although both the basic concept of the median filter and its use in the field of image processing are well known, many prior realizations have depended upon timeconsuming software routines.
Prior-art network concepts which are capable of being mechanized as hardware-economical, ordinal-value filters which perform their Mth-largest determination at the incoming data rate are presented by D. Knuth in Vol. 3 of his book The Art of Computer Programming: Sorting and Searching (1973). See especially the odd-even transposition sorting networks given in Knuth's FIG. 58 on page 241.
It should be noted, however, that the inventions claimed in this specification are considered to be patentably different from Knuth's concepts, as well as from the network concepts and mechanizations presented in the incorporated applications.
A real-time, ordinal-value-filtering capability is extremely useful, especially, for example, in those situations where the ordinal-value processing of dynamic images is of greatest value when it can be performed as the images are occurring.